package ch.ethz.fcl.metrobuzz.algorithm.sort.heapsort;

import java.util.ArrayList;
import java.util.List;

import ch.ethz.fcl.metrobuzz.algorithm.sort.ISort;
import ch.ethz.fcl.metrobuzz.algorithm.sort.SortData;

public class HeapSort implements ISort {
	public List<SortData> unsorteddatas;
	private List<SortData> sortedDatas;

	private int n;
	private int left;
	private int right;
	private int largest;

	public HeapSort() {
		unsorteddatas = new ArrayList<SortData>();
	}

	public HeapSort(float[] num) {
		unsorteddatas = new ArrayList<SortData>();
		if (num != null)
			for (int i = 0; i < num.length; i++)
				addNum(num[i]);
	}

	@Override
	public void addNum(float num) {
		SortData data = new SortData(num, unsorteddatas.size());
		unsorteddatas.add(data);
	}

	@Override
	public void addData(SortData data) {
		unsorteddatas.add(data);
	}

	@Override
	public List<SortData> getSortedData() {
		if (sortedDatas != null)
			return sortedDatas;
		else {
			sort(unsorteddatas);
			return sortedDatas;
		}
	}

	public List<SortData> getUnsortedData() {
		return unsorteddatas;
	}

	private void buildheap(List<SortData> a) {
		n = a.size() - 1;
		for (int i = n / 2; i >= 0; i--)
			maxheap(a, i);
	}

	private void maxheap(List<SortData> a, int i) {
		left = 2 * i;
		right = 2 * i + 1;
		if (left <= n && a.get(left).getValue() > a.get(i).getValue()) {
			largest = left;
		} else {
			largest = i;
		}

		if (right <= n && a.get(right).getValue() > a.get(largest).getValue()) {
			largest = right;
		}
		if (largest != i) {
			exchangelist(i, largest);
			maxheap(a, largest);
		}
	}

	private void sort(List<SortData> in) {
		sortedDatas = new ArrayList<SortData>(unsorteddatas);
		buildheap(sortedDatas);

		for (int i = n; i > 0; i--) {
			exchangelist(0, i);
			n = n - 1;
			maxheap(sortedDatas, 0);
		}
	}

	private void exchangelist(int i, int j) {
		SortData t = sortedDatas.get(i);
		sortedDatas.add(i, sortedDatas.get(j));
		sortedDatas.remove(i + 1);
		sortedDatas.add(j, t);
		sortedDatas.remove(j + 1);
	}
}
